package com.atguigu.distributed.lock.leecode.tree;

import com.atguigu.distributed.lock.leecode.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 力扣中等662二叉树最大宽度
 */
public class WidthOfBinaryTree {
    Map<Integer, Integer> levelMin = new HashMap<>();
    public int widthOfBinaryTree(TreeNode root){
        return dfs(root,1,1);
    }
    public int dfs(TreeNode node,int depth,int index){
        if(node==null){
            return 0;
        }
        levelMin.putIfAbsent(depth,index);//每一层最先访问到的节点会是最左边的节点，即编号最小的节点
        return Math.max(index-levelMin.get(depth)+1,Math.max(dfs(node.left,depth+1,index*2),
                dfs(node.right,depth+1,index*2+1)));
    }
}
